package _11_整理题目._5_贪心;

import org.junit.Test;

/**
 * https://leetcode-cn.com/problems/monotone-increasing-digits/
 *
 * 给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
 * 当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
 *
 * 思路一：逐个尝试，比较（超时）
 *
 * 思路二：贪心
 *      我们可以从高到低按位构造这个小于等于 n 的最大单调递增的数字
 *      假设不考虑 nn 的限制，那么对于一个长度为 kk 的数字，最大单调递增的数字一定是每一位都为 9 的数字。
 *
 *      // 例 77616726
 *      先找到 不满足递增的 索引位 i=2，如果没有，直接返回
 *      让当前位 减一，并检查前面的 位置是否满足，不满足减一
 *      当前位+1，让后面的位全赋值 9
 */
public class _01_单调递增的数字 {

    // 77616726
    public int monotoneIncreasingDigits(int num) {
        char[] str = (num+"").toCharArray();
        int n = str.length;
        int i = 0;
        while(i<n-1 && str[i]<=str[i+1]) {
            i++;
        }

        if(i < n-1) {
            while(i>=0 && str[i] > str[i+1]) {
                str[i]--;
                i--;
            }
            i += 2;
            while(i < n) {
                str[i] = '9';
                i++;
            }
        }

        return Integer.parseInt(new String(str));
    }

    @Test
    public void main() {
        System.out.println(monotoneIncreasingDigits(77616726));
    }

}
